package com.heima.datastructure.queue;

import java.util.Iterator;

/**
 * <h3>用环形数组实现队列 方法二：用size记录大小</h3>
 *
 * @param <E>
 */
public class ArrayQueue2<E> implements Queue<E>, Iterable<E> {
    private E[] arr; // 环形数组
    private int head; // 头指针，指向头元素
    private int tail; // 尾指针，指向尾元素的下一个
    private int size; // 队列长度大小

    /**
     * 用构造器初始化
     *
     * @param capacity 数组容量
     */
    @SuppressWarnings("all")
    public ArrayQueue2(int capacity) {
        arr = (E[]) new Object[capacity];
        head = 0;
        tail = 0;
        size = 0;
    }

    /**
     * 向队列尾部添加
     * @param value 待插入值
     * @return 是否添加成功
     */
    @Override
    public boolean offer(E value) {
        if (isFull()){
            return false;
        }
        arr[tail] = value;
        tail = (tail + 1) % arr.length;
        size++;
        return true;
    }

    /**
     * 获取队列第一个元素的值，并且删掉
     * @return 第一个元素的值
     */
    @Override
    public E poll() {
        if (isEmpty()){
            return null;
        }
        E value = arr[head];
        // 如果是基本类型，不用释放，例如int初始化为0还是四个字节，
        // 但是这里用了泛型，未来会被具体的对象替代，数组里面存的指针（对象的地址），
        // 指针指向这个对象，属于引用类型，该数组元素指向一个对象实例，
        // 当对象实例没有人指向它时才会被垃圾回收，所以这里要去掉指向该对象实例的指针
        arr[head] = null;
        head = (head + 1) % arr.length;
        size--;
        return value;
    }

    @Override
    public E peek() {
        if (isEmpty()){
            return null;
        }
        return arr[head];
    }

    /**
     * 判断是否为空
     * @return 是否为空
     */
    @Override
    public boolean isEmpty() {
        return size == 0;
    }

    /**
     * 判断是否为满
     * @return 是否为满
     */
    @Override
    public boolean isFull() {
        return size == arr.length;
    }

    /**
     * 迭代器
     * @return 迭代器
     */
    @Override
    public Iterator<E> iterator() {
        return new Iterator<E>() {
            int index = head;
            int count = 0;
            @Override
            public boolean hasNext() {
                return count < arr.length;
            }

            @Override
            public E next() {
                E value = arr[index];
                index = (index + 1) % arr.length;
                count++;
                return value;
            }
        };
    }

    /**
     * 获取队列大小
     * @return 队列大小
     */
    public int size(){
        return size;
    }

    /**
     * 扩容
     * @param capacity 扩展到的容量
     */
    @SuppressWarnings("all")
    public void expansion(int capacity){
        if (capacity < arr.length){
            throw new IllegalArgumentException("参数 [" + capacity + "] 不能比" + arr.length + "小");
        }
        E[] array = (E[]) new Object[capacity];
        int index = 0, count = 0;
        for (int i = head; count < size; i = (i + 1) % arr.length, count++){
            array[index] = arr[i];
            index++;
        }
        head = 0;
        tail = index;
        arr = array;
    }
}
